This section is intended to provide a background or context. The description may include concepts that may be pursued, but have not necessarily been previously conceived or pursued. Unless indicated otherwise, what is described in this section is not deemed prior art to the description and claims, and is not admitted to be prior art by inclusion in this section.
In 1971, Leon Chua postulated the existence of a new circuit element. The three basic two-terminal circuit elements then known connect pairs of the four circuit variables: current, i; voltage, v; charge, q; and magnetic flux, φ. Five relationships combining these variables were known: (i) the definition of current and the definition of voltage from the induction law of Faraday, and (ii) the three axiomatic definitions of the known circuit elements. Chart 100 of FIG. 1 shows the relations between different elements and physical properties of circuits. Chua argued completeness required a sixth relationship 110, which would define the missing circuit element. Chua called it ‘memristor’, a contraction of memory and resistor, for its behavior was somewhat like that of a nonlinear resistor with memory.
Not until 2008 was it physically realized by Stanley Williams and his team at HP Labs (see further: Dmitri B Strukov, Gregory S Snider, Duncan R Stewart, and R Stanley Williams. The missing memristor found. Nature, 453(7191):80-83, 2008). Since then, much research has sought to exploit its properties, from a quest for memristive memories, to memristive devices for neuromorphic computing, to computational logic that uses memristors as logic gates.
The evaluation of Boolean formulas, which has garnered some recent attention, is an enabling technology for synthesizing high-performance, low-power arithmetic and logic circuits.
There is much literature on memristive evaluation of Boolean formulas. Some representative work in this area includes Julien Borghetti, Gregory S Snider, Philip J Kuekes, J Joshua Yang, Duncan R Stewart, and R Stanley Williams ‘Memristive’ switches enable ‘stateful’ logic operations via material implication, Nature, 464(7290):873-876, 2010. Borghetti, et al. use two memristors to compute material implication, a fundamental operation in Boolean logic. They leverage this design to synthesize a universal NAND gate using three memristors and three time steps, one initialization step and two implication steps. Another article, Ella Gale, Ben de Lacy Costello, and Andrew Adamatzky. Boolean logic gates from a single memristor via low-level sequential logic. In Unconventional Computation and Natural Computation, pages 79-89, Springer, 2013, describes a single memristor, through which two pulses pass sequentially, with the second being sent before the current spike generated by the first stabilizes. The logical value true is obtained when the current spike goes past a threshold. These designs have two fundamental problems. First, they use a few memristors interacting with other non-memristive circuit elements. It is difficult to put such a heterogeneous mixture of circuit elements on the same hybrid chip. Second, they rely on a sequence of correctly timed inputs, requiring a global clock. Such synchronous extreme-scale circuits are notoriously difficult to design.
For purposes of fabrication, rather than using a few individual memristors, it is more natural to organize sets of them into crossbar networks. However, if the design or application requires that memristors be addressed individually, then the sneak-path problem arises: current flows through unknown paths in parallel to the memristor of interest, which prevents correct detection of its resistance or the flow of current through it. Much research is being devoted to overcoming this problem. The previously proposed solutions often unavoidably increase the complexity of the fabrication process.